package leetcode;

import list.LinkedListCreate;
import list.ListNode;

public class PartitionList {

	public static void main(String[] args) {
		PartitionList object = new PartitionList();
		int[] array = {1, 4, 3, 2, 5, 2};
		ListNode head = LinkedListCreate.createList(array);
		head = object.partition(head, 3);
		LinkedListCreate.printList(head);
	}
	
	public ListNode partition(ListNode head, int x) {
		if (head == null) {
			return null;
		}
		ListNode less = new ListNode(0);
		ListNode more = new ListNode(0);
		ListNode lessHead = less;
		ListNode moreHead = more;
		ListNode temp = head;
		while (temp != null) {
			if (temp.val < x) {
				less.next = new ListNode(temp.val);
				less = less.next;
			} else {
				more.next = new ListNode(temp.val);
				more = more.next;
			}
			temp = temp.next;
		}
		LinkedListCreate.printList(lessHead);
		LinkedListCreate.printList(moreHead);
		less.next = moreHead.next;
		return lessHead.next;
	}
}
